Incentivized social advertising, an emerging marketing model, providesmonetization opportunities not only to the owners of the social networkingplatforms but also to their influential users by offering a "cut" on theadvertising revenue. We consider a social network (the host) that sellsad-engagements to advertisers by inserting their ads, in the form of promotedposts, into the feeds of carefully selected "initial endorsers" or seed users:these users receive monetary incentives in exchange for their endorsements. Theendorsements help propagate the ads to the feeds of their followers. In thiscontext, the problem for the host is is to allocate ads to influential users,taking into account the propensity of ads for viral propagation, and carefullyapportioning the monetary budget of each of the advertisers between incentivesto influential users and ad-engagement costs, with the rational goal ofmaximizing its own revenue. We consider a monetary incentive for theinfluential users, which is proportional to their influence potential. We showthat revenue maximization in incentivized social advertising corresponds to theproblem of monotone submodular function maximization, subject to a partitionmatroid constraint on the ads-to-seeds allocation, and submodular knapsackconstraints on the advertisers' budgets. This problem is NP-hard and we devise2 greedy algorithms with provable approximation guarantees, which differ intheir sensitivity to seed user incentive costs. Our approximation algorithmsrequire repeatedly estimating the expected marginal gain in revenue as well asin advertiser payment. By exploiting a connection to the recent advances madein scalable estimation of expected influence spread, we devise efficient andscalable versions of the greedy algorithms.
展开▼
